package codingInterview.leetcode.editor.cn;

//数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，
//等等。 
//
// 请写一个函数，求任意第n位对应的数字。 
//
// 
//
// 示例 1： 
//
// 输入：n = 3
//输出：3
// 
//
// 示例 2： 
//
// 输入：n = 11
//输出：0 
//
// 
//
// 限制： 
//
// 
// 0 <= n < 2^31 
// 
//
// 注意：本题与主站 400 题相同：https://leetcode-cn.com/problems/nth-digit/ 
// Related Topics 数学 二分查找 👍 216 👎 0

//Java：剑指 Offer 44 - 数字序列中某一位的数字
public class ShuZiXuLieZhongMouYiWeiDeShuZiLcof{
    public static void main(String[] args) {
                Solution solution = new ShuZiXuLieZhongMouYiWeiDeShuZiLcof().new Solution();
        // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int findNthDigit(int n) {
        if(n<10) return n;
        int rest=n, i=1;
        while(rest>9*i*Math.pow(10,i-1)){
            rest-=9*i*Math.pow(10,i-1); // 去掉前面i位数的集合
            i++;
        }
        // 此时 变成找i位数集合中第rest位的数
        int num = rest/i;
        rest%=i;
        if(rest==0){
            num = (int)Math.pow(10,i-1)+num-1; //重组n应在的数字
            return num%10;// 结果为num的最后一位数
        }else{
            num = (int)Math.pow(10,i-1)+num; //重组n应在的数字
            return num/(int)Math.pow(10,i-rest)%10; //结果为num的第rest位数
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
